package 剑指offer.树;

import java.util.Arrays;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。
 * 假设输入的数组的任意两个数字都互不相同。
 */
public class 第33题二叉搜索树的后序遍历序列 {

    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return isLRD(sequence, sequence.length);
    }

    /**
     * 现有 LRD 序列：{5, 7, 6, 9, 11, 10, 8}
     * 8 是根节点，由二叉搜索树的特点可知，根节点左孩子小于他，右孩子大于他
     * 于是可以找到根节点之下的两个子节点分别是：5,7,6 和 9,11,10
     * 这两组又是一颗二叉搜索树，按照规律处理一次得到根节点6和10，以及他们的左右子树5,7和9,11
     * 在整个处理过程中所有数据均符合二叉搜索树的约定，于是返回 true
     *
     * 一旦发现有节点不符合约定返回 false
     *
     * @param sequence LRD 序列
     * @param length 数组的长度
     * @return
     */
    private boolean isLRD(int[] sequence, int length) {
        // 1. 找到根节点
        int root = sequence[length - 1];
        // 2. 找到左右子树分界线
        int i = 0;
        for (; i < length - 1; i++) {
            if (sequence[i] > root)
                break;
        }
        // 3. 此时的 i 就是右子树的第一个节点
        // 理想化的左子树已经遍历完毕（即左子树节点全部小于根节点），先检查右子树是否合法
        for (int j = i; j < length - 1; j++) {
            if (sequence[j] < root) {
                return false;
            }
        }
        // 现在得到了理想化的右子树，但是还不行。只判断一次大小不够，需要递归下去分解到单个元素才算完

        // 4. 递归处理左子树，检查合法性
        boolean res1 = true;
        if (i > 0) {
            res1 = isLRD(sequence, i);
        }
        // 5. 递归处理右子树，检查合法性
        boolean res2 = true;
        if (i < length - 1) {
            res2 = isLRD(Arrays.copyOfRange(sequence, i, length - 1), length - i - 1);
        }
        // 有一处不合法就要返回 false
        return res1 && res2;
    }
}
